from BM import BoyerMoore
from KMP import KnuthMorrisPratt
import BM, KMP

import random, time, os

def println(str, meta = '*', total = 80):
	tmp = total - len(str)
	if tmp % 2 == 0:
		left = tmp / 2
		right = left
	else:
		left = tmp / 2
		right = total - len(str) - left
	print meta * left + str + meta * right



def main():
	# text = 'bbc abcdab abcdabcdabde'
	# pattern = 'abcdabd'
	# print 'BM VS KMP'
	# println('BM')
	# BoyerMoore(text, pattern, True)
	# println('KMP')
	# KnuthMorrisPratt(text, pattern, True)
	# println('')

	testTextLen = 10000000
	testPatternLen = 1000

	testText = ''.join(map(lambda xx:(hex(ord(xx))[2:]),os.urandom(testTextLen)))
	while True:
		a = random.randint(0, testTextLen)
		if a < testTextLen - testPatternLen:
			break
	testPattern = testText[a:a + testPatternLen]

	# use for testing
	# for i in range(100000):
	# 	try :
	# 		testText = ''.join(map(lambda xx:(hex(ord(xx))[2:]),os.urandom(testTextLen)))
	# 		while True:
	# 			a = random.randint(0, testTextLen)
	# 			if a < testTextLen - testPatternLen:
	# 				break
	# 		testPattern = testText[a:a + testPatternLen]
	# 		assert(testText.find(testPattern) == BoyerMoore(testText, testPattern))
	# 	except:
	# 		print testText
	# 		print testPattern
	# 		break

	print 'begin find...'
	start = time.time()
	findResult = testText.find(testPattern)
	end = time.time()
	findTime = end - start

	print 'begin KMP...'
	start = time.time()
	kmpResult = KnuthMorrisPratt(testText, testPattern)
	end = time.time()
	kmpTime = end - start

	print 'begin BM...'
	start = time.time()
	bmResult = BoyerMoore(testText, testPattern)
	end = time.time()
	bmTime = end - start
	println('find ' + str(testPatternLen) + ' in ' + str(testTextLen))
	println('position', '-', 50)
	print 'find ', findResult
	print 'KMP  ', kmpResult
	print 'BM   ', bmResult
	println('build Shift table time', '-', 50)
	print 'KMP  ', KMP.buildShiftTime
	print 'BM   ', BM.buildShiftTime
	println('time', '-', 50)
	print 'find ', findTime, 's'
	print 'KMP  ',kmpTime, 's'
	print 'BM   ', bmTime, 's'
	println('move times', '-', 50)
	print 'KMP  ', KMP.count
	print 'BM   ', BM.count
	println('')

if __name__ == '__main__':
	main()